package ali;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author wxh
 */
public class Solution_22 {

	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		List<List<Integer>> ans = new ArrayList<List<Integer>>();
		List<Integer> combine = new ArrayList<Integer>();
		dfs(candidates, target, ans, combine, 0);
		return ans;
	}

	/**
	 * 递归函数 dfs表示当前在 candidates 数组的第 idx 位，还剩 target 要组合，已经组合的列表为 combine
	 * @param candidates 数组
	 * @param target  目前值
	 * @param ans 	  结果集
	 * @param combine 已组合的列表
	 * @param idx
	 */
	public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {

		//递归的终止条件： target <= 0 或者 candidates 数组被全部用完
		if (idx == candidates.length) {
			return;
		}

		//target == 0 则保存结果集
		if (target == 0) {
			ans.add(new ArrayList<Integer>(combine));
			return;
		}

		// 直接跳过
		dfs(candidates, target, ans, combine, idx + 1);

		int remain = target - candidates[idx];
		if (remain >= 0) {
			combine.add(candidates[idx]); // 符合条件，则加入已组合的列表
			dfs(candidates,remain , ans, combine, idx); //继续递归查找符合条件的
			combine.remove(combine.size() - 1);
		}
	}

	public static void main(String[] args) {
		Solution_22 solution_22 = new Solution_22();
		System.out.println(solution_22.combinationSum(new int[]{2,3,6,7},7));
	}

}